/**
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * <p>
 * 整数 a 比整数 b 更接近 x 需要满足：
 * <p>
 * <p>
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
 * 输出：[1,2,3,4]
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 1 <= k <= arr.length
 * 1 <= arr.length <= 10⁴
 * <p>
 * arr 按 升序 排列
 * -10⁴ <= arr[i], x <= 10⁴
 * <p>
 * <p>
 * Related Topics 数组 双指针 二分查找 排序 滑动窗口 堆（优先队列） 👍 457 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

import java.util.*;

public class ID00658FindKClosestElements {
    public static void main(String[] args) {

        Solution solution = new ID00658FindKClosestElements().new Solution();
        solution.findClosestElements(new int[]{1, 1, 1, 10, 10, 10}, 1, 9);
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            int len = arr.length;

            int left = 0;
            int right = len - 1;

            //peek value in this range
            int startIndex = -1;
            int endIndex = -1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (arr[mid] == x) {
                    startIndex = mid;
                    break;
                } else if (arr[mid] < x) {
                    left = mid + 1;
                } else if (arr[mid] > x) {
                    right = mid - 1;
                }
            }

            if (startIndex < 0) { //没找到mid
                if (right < 0) {
                    startIndex = 0;
                    endIndex = k - 1;
                } else if (left == len) {
                    startIndex = len - k;
                    endIndex = len - 1;
                } else {
                    //左右延展k个，搜索范围是2k
                    startIndex = Math.max(right - k + 1, 0); //right落在小于x的第一个
                    endIndex = Math.min(left + k - 1, len - 1);//left落在大于x的第一个
                }
            } else { //找到mid了, 结果必包含mid
                startIndex = Math.max(startIndex - k + 1, 0);
                endIndex = Math.min(startIndex + 2 * k - 1, len - 1);

            }


            //范围内找用大顶堆找出最接近x的k个值

            PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Math.abs(o2 - x) - Math.abs(o1 - x);
                }
            });

            int i = startIndex;

            while (i < startIndex + k) { //先放进去k个
                queue.add(arr[i]);
                i++;
            }

            while (i <= endIndex) {
                int nowInt = arr[i];
                int topInt = queue.peek();
                if (Math.abs(nowInt - x) < Math.abs(topInt - x)) {
                    queue.poll();
                    queue.add(nowInt);
                }
                i++;


            }


            //堆内元素返回
            List<Integer> res = new ArrayList<>(k);
            res.addAll(queue);
            Collections.sort(res);
            return res;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}